package com.shigen.demo.datastruct.tree.impl;

import com.shigen.demo.datastruct.tree.AbstractTree;
import com.shigen.demo.datastruct.tree.Node;
import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 实现类
 *
 * @author shigenfu
 * @date 2022/7/12 4:08 下午
 */
public class AbstractTreeImpl implements AbstractTree {

  @Override
  public void preOrder(Node root) {
    if (root == null) {
      return;
    }
    System.out.print(root.data + " ");
    preOrder(root.leftNode);
    preOrder(root.rightNode);
  }

  @Override
  public void inOrder(Node root) {
    if (root == null) {
      return;
    }
    inOrder(root.leftNode);
    System.out.print(root.data + " ");
    inOrder(root.rightNode);
  }

  @Override
  public void postOrder(Node root) {
    if (root == null) {
      return;
    }
    postOrder(root.leftNode);
    postOrder(root.rightNode);
    System.out.print(root.data + " ");
  }

  @Override
  public int getNodeCount(Node root) {
    if (root == null) {
      return 0;
    }
    return 1 + getNodeCount(root.leftNode) + getNodeCount(root.rightNode);
  }

  @Override
  public int getLeafNodeCount(Node root) {
    if (root == null) {
      return 0;
    }
    if (root.leftNode == null && root.rightNode == null) {
      return 1;
    }
    return getNodeCount(root.leftNode) + getNodeCount(root.rightNode);
  }

  @Override
  public int getHeight(Node root) {
    if (root == null) {
      return 0;
    }
    return 1 + Math.max(getHeight(root.leftNode), getHeight(root.rightNode));
  }

  @Override
  public boolean contains(Node root, int val) {
    if (root == null) {
      return false;
    }
    if (root.data == val) {
      return true;
    }
    return contains(root.leftNode, val) || contains(root.rightNode, val);
  }

  @Override
  public int getKLevelNode(Node root, int k) {
    if (k <= 0 || root == null) {
      return 0;
    }
    if (k == 1) {
      return 1;
    }
    return getKLevelNode(root.leftNode, k - 1) + getKLevelNode(root.rightNode, k - 1);
  }

  @Override
  public Node addRecursive(Node root, int data) {
    if (root == null) {
      return new Node(data);
    }
    if (data < root.data) {
      root.leftNode = addRecursive(root.leftNode, data);
    } else if (data > root.data) {
      root.rightNode = addRecursive(root.rightNode, data);
    }
    return root;
  }

  @Override
  public Node getNode(Node root, int value) {
    if (root == null) {
      return null;
    }
    if (value < root.data) {
      return getNode(root.leftNode, value);
    } else if (value > root.data) {
      return getNode(root.rightNode, value);
    } else {
      return root;
    }
  }

  @Override
  public Node deleteNode(Node root, int value) {
    if (root == null) {
      return null;
    }
    if (root.data == value) {
      // 左右节点都是空的，此根节点为空
      if (root.leftNode == null && root.rightNode == null) {
        return null;
      }
      if (root.leftNode == null) {
        return root.rightNode;
      }
      if (root.rightNode == null) {
        return root.leftNode;
      }
    }

    if (value < root.data) {
      root.leftNode = deleteNode(root.leftNode, value);
      return root;
    }
    root.rightNode = deleteNode(root.rightNode, value);
    return root;
  }

  @Override
  public void traverseLevelOrder(Node root) {
    if (root == null) {
      return;
    }
    Queue<Node> nodes = new ArrayDeque<>();
    nodes.add(root);

    while (!nodes.isEmpty()) {
      Node node = nodes.remove();
      System.out.print(" " + node.data);
      if (node.leftNode != null) {
        nodes.add(node.leftNode);
      }
      if (node.rightNode != null) {
        nodes.add(node.rightNode);
      }
    }


  }
}
